package jp.tkym.labs.coder;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;


/**
 * Manao has been to a tremendous candy shop several times. He has forgotten 
 * its exact placement, but remembers some information about each time he 
 * visited the shop.
 * 
 * The city Manao lives in can be represented as an infinite two-dimensional 
 * plane with a Cartesian coordinate system. From point (x, y), Manao can move 
 * to any of the points (x - 1, y), (x, y - 1), (x + 1, y), or (x, y + 1). 
 * In order to perform each of these 4 moves, he needs to walk 1 unit of 
 * length. Manao recalls that the candy shop was located at a point with 
 * integer coordinates. Also, he remembers that the i-th time he visited 
 * the candy shop, he went there from point (X[i], Y[i]) and walked at most 
 * R[i] units of length.
 * 
 * 
 * Since Manao's visits to the shop span a long period of time, he may have 
 * misremembered some details. If no intersection complies with his reminiscence, 
 * return 0. Otherwise return the number of different intersections where 
 * Manao's candy shop could be, assuming Manao remembers everything correctly.
 * 
 * 
 * @author takayama
 *
 */
public class Srm508R1Div2Lv1 {
	@Test
	public void case000(){
		CandyShop candyShop = new CandyShop();
		List<Point> result = candyShop.createPointList(0, 0, 0);
		assertThat(result.size(), is(1));
		assertThat(result.get(0).x, is(0));
		assertThat(result.get(0).y, is(0));
	}
	
	@Test
	public void case001(){
		CandyShop candyShop = new CandyShop();
		List<Point> result = candyShop.createPointList(0, 0, 1);
		assertThat(result.get(0).x, is(0));
		assertThat(result.get(0).y, is(-1));
		assertThat(result.get(1).x, is(-1));
		assertThat(result.get(1).y, is(0));
		assertThat(result.get(2).x, is(0));
		assertThat(result.get(2).y, is(0));
		assertThat(result.get(3).x, is(1));
		assertThat(result.get(3).y, is(0));
		assertThat(result.get(4).x, is(0));
		assertThat(result.get(4).y, is(1));
	}
	
	
	@Test
	public void intersectCase001(){
		List<Point> a = new ArrayList<Point>();
		a.add(new Point(0, 0));
		a.add(new Point(0, 1));
		a.add(new Point(1, 0));
		
		List<Point> b = new ArrayList<Point>();
		b.add(new Point(0, 0));
		b.add(new Point(0, 1));
		b.add(new Point(2, 0));
		b.add(new Point(0, -1));
		
		CandyShop candyShop = new CandyShop();
		List<Point> result = candyShop.intersectAxis(a, b);
		assertThat(result.size(), is(2));
		assertThat(result.get(0).x, is(0));
		assertThat(result.get(0).y, is(0));
		assertThat(result.get(1).x, is(0));
		assertThat(result.get(1).y, is(1));
	}
	
	@Test
	public void countProbablePlacesCase000(){
		CandyShop candyShop = new CandyShop();
		int result = candyShop.countProbablePlaces(
				new int[]{0}, 
				new int[]{0}, 
				new int[]{1});
		assertThat(result, is(5));
	}
	
	@Test
	public void countProbablePlacesCase001(){
		CandyShop candyShop = new CandyShop();
		int result = candyShop.countProbablePlaces(
				new int[]{0}, 
				new int[]{0}, 
				new int[]{2});
		assertThat(result, is(13));
	}
	
	@Test
	public void countProbablePlacesCase002(){
		CandyShop candyShop = new CandyShop();
		int result = candyShop.countProbablePlaces(
				new int[]{2, 3}, 
				new int[]{1,-1}, 
				new int[]{2, 2});
		assertThat(result, is(4));
	}
	
	@Test
	public void countProbablePlacesCase003(){
		CandyShop candyShop = new CandyShop();
		int result = candyShop.countProbablePlaces(
				new int[]{2, 3, 5}, 
				new int[]{1,-1, 0}, 
				new int[]{2, 2, 3});
		assertThat(result, is(3));
	}
	
	@Test
	public void countProbablePlacesCase004(){
		CandyShop candyShop = new CandyShop();
		int result = candyShop.countProbablePlaces(
				new int[]{2, 3, 5}, 
				new int[]{1,-1, 0}, 
				new int[]{2, 2, 3});
		assertThat(result, is(3));
	}
	
	@Test
	public void countProbablePlacesCase006(){
		CandyShop candyShop = new CandyShop();
		int result = candyShop.countProbablePlaces(
				new int[]{-3, 3, 5, 5}, 
				new int[]{ 4, 5,-2, 0}, 
				new int[]{10,11, 8, 6});
		assertThat(result, is(33));
	}

	public class CandyShop{
		public int countProbablePlaces(int[] X, int[] Y, int[] R){
			if(X.length != Y.length)
				throw new IllegalArgumentException("X.length != Y.length");
			if(R.length != Y.length)
				throw new IllegalArgumentException("R.length != Y.length");
			List<Point> result = new ArrayList<Point>();
			for(int i=0; i<X.length; i++){
				List<Point> list = createPointList(X[i], Y[i], R[i]);
				if(i==0) {
					result.addAll(list);
				} else {
					result = intersectAxis(result, list);
				}
			}
			return result.size();
		}
		
		List<Point> intersectAxis(List<Point> a, List<Point> b){
			List<Point> result = new ArrayList<Point>();
			for(Point aa : a)
				for(Point bb : b)
				if(aa.equals(bb))
					result.add(aa);
			return result;
		}
		
		List<Point> createPointList(int x, int y, int r){
			List<Point> result = new ArrayList<Point>();
			
			if(r<0) throw new IllegalArgumentException("r<0");
			
			for(int yi=-r; yi<=r; yi++){
				int yd = yi;
				if(yi < 0) yd = -yi;
				for(int xi=(yd-r); xi<=(r-yd); xi++)
					result.add(new Point(x+xi, y+yi));
			}
			return result;
		}
	}
	
	class Point{
		int x;
		int y;
		
		Point(int x, int y){
			this.x = x;
			this.y = y;
		}
		
		@Override
		public boolean equals(Object obj) {
			if(obj == null)
				return false;
			if(!(obj instanceof Point))
				return false;
			Point other = (Point) obj;
			
			if(this.x != other.x) return false;
			if(this.y != other.y) return false;
			
			return true;
		}
	}
}